package com.gxc.array;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 18. 四数之和
 * 给你一个由 n 个整数组成的数组 nums ，和一个目标值 target 。
 * 请你找出并返回满足下述全部条件且不重复的四元组
 * [nums[a], nums[b], nums[c], nums[d]]
 * （若两个四元组元素一一对应，则认为两个四元组重复）：
 *
 * 0 <= a, b, c, d < n
 * a、b、c 和 d 互不相同
 * nums[a] + nums[b] + nums[c] + nums[d] == target
 * 你可以按 任意顺序 返回答案 。
 *
 * 1 <= nums.length <= 200
 * -109 <= nums[i] <= 109
 * -109 <= target <= 109
 * 越界问题
 */
public class FourSum {

    public static void main(String[] args) {
        int[] nums = {0,0,0,1000000000,1000000000,1000000000,1000000000};
        int target = 1000000000;
        print(handle(nums, target));
    }

    //4层循环
    public static List<List<Integer>> handle(int[] nums, int target) {
        List<List<Integer>> res = new ArrayList<>();
        if (nums == null || nums.length < 4) return res;

        Arrays.sort(nums);
        int max = Integer.MAX_VALUE;
        int min = Integer.MIN_VALUE;
        for (int i = 0; i < nums.length-3; i++) {
            if (i > 0 && nums[i] == nums[i-1]) continue;

            if ((long)nums[i] + nums[i+1] + nums[i+2] + nums[i+3] > target) break;
            if ((long)nums[i] + nums[nums.length-3] + nums[nums.length-2] + nums[nums.length-1] < target) continue;

             for (int j = i+1; j < nums.length-2; j++) {
                 if (j > i+1 && nums[j] == nums[j-1]) continue;
                 int left = j+1;
                 int right = nums.length-1;
                 if ((long) nums[i] + nums[j] + nums[j + 1] + nums[j + 2] > target) {
                     break;
                 }
                 if ((long) nums[i] + nums[j] + nums[nums.length - 2] + nums[nums.length - 1] < target) {
                     continue;
                 }
                 while (left<right) {
                     int sum = nums[i] + nums[j] + nums[left] + nums[right];
                     if (sum == target) {
                         List<Integer> list = new ArrayList<>();
                         list.add(nums[i]);
                         list.add(nums[j]);
                         list.add(nums[left]);
                         list.add(nums[right]);
                         res.add(list);

                         while (left<right && nums[left] == nums[left+1]) {
                             left++;
                         }
                         left++;
                         while (left<right && nums[right] == nums[right-1]) {
                             right--;
                         }
                         right--;
                     } else if (sum>target){
                         right--;
                     } else {
                         left++;
                     }
                 }
            }
        }
        return res;
    }

    private static void print(List<List<Integer>> res) {
        if (res == null) return;
        for (int i = 0; i < res.size(); i++) {
            List<Integer> integers = res.get(i);
            for (int j = 0; j < integers.size(); j++) {
                System.out.print(integers.get(j) + " ");
            }
            System.out.println("");
        }
    }
}
